package 中等.数学;

/**
 * 给定一个表示分数加减运算的字符串 expression ，你需要返回一个字符串形式的计算结果。 
 * 这个结果应该是不可约分的分数，即最简分数。 如果最终结果是一个整数，例如 2，你需
 * 要将它转换成分数形式，其分母为 1。所以在上述例子中, 2 应该被转换为 2/1。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/fraction-addition-and-subtraction
 */
public class 分数加减运算_592 {

    public static void main(String[] args) {

        System.out.println(fractionAddition("3/1-9/7+10/3-10/7-5/7"));

    }

    /**
     * 模拟
     * x1/x2 + x3/x4 = (x1*x4 + x3*x2) / x2*x4
     *
     * @param expression
     * @return
     */
    public static String fractionAddition(String expression) {
        int x1 = 0;
        int x2 = 1;
        int left = 0;
        while (left < expression.length()) {
            int right = left + 1;
            while (right < expression.length() && expression.charAt(right) != '+' &&
                    expression.charAt(right) != '-') right++;

            String[] split = expression.substring(left, right).split("/");
            Integer x3 = Integer.valueOf(split[0]);
            Integer x4 = Integer.valueOf(split[1]);

            int tx1 = x1, tx2 = x2;
            x1 = tx1 * x4 + x3 * tx2;
            x2 = tx2 * x4;

            int commonDivisor = getMaxCommonDivisor(x1, x2);
            while (commonDivisor > 1) {
                x1 /= commonDivisor;
                x2 /= commonDivisor;
                commonDivisor = getMaxCommonDivisor(x1, x2);
            }
            left = right;
        }
        return x1 == 0 ? "0/1" : x1 + "/" + x2;
    }

    // 最大公约数
    private static int getMaxCommonDivisor(int a, int b) {
        if (a == b) return a;
        a = Math.abs(a);
        b = Math.abs(b);
        int twoSquare = 1;
        while (a % 2 == 0 && b % 2 == 0) {
            a /= 2;
            b /= 2;
            twoSquare *= 2;
        }
        int min = Math.min(a, b), max = Math.max(a, b);
        while (min > 1) {
            int sub = max - min;
            if (sub == min) {
                break;
            }
            int tempMin = min;
            min = Math.min(tempMin, sub);
            max = Math.max(tempMin, sub);
        }
        return twoSquare * min;
    }

}
